package month1;
import java.util.*;
public class GenerateParenthesis22_06 {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }

    static List<String> generateParenthesis(int n) {
        List<String> ret = new ArrayList<>();
        traceback(n, ret, 0, 0, "");
        return ret;
    }
    static void traceback(int n, List<String> ret, int l, int r, String tmp) {
        if (tmp.length() == 2 * n) {
            ret.add(tmp);
            return;
        }
        if (l < n) {
            traceback(n, ret, l + 1, r, tmp + "(");
        }
        if (r < l) {
            traceback(n, ret, l, r + 1, tmp + ")");
        }
    }
}
